In general, a chaotic system is a dynamical system which has no periodicity and the final state of which depends so sensitively on the system's precise initial state that its time-dependent path is, in effect, long-term unpredictable even though it is deterministic.
One approach to chaotic communication, Short, et al., Method and Apparatus for Secure Digital Chaotic Communication, U.S. patent application Ser. No. 09/436,910 (“Short I”), describes a chaotic system controlled by a transmitter/encoder and an identical chaotic system controlled by a receiver/decoder. Communication is divided into two steps: initialization and transmission. The initialization step uses a series of controls to drive the identical chaotic systems in the transmitter/encoder and receiver/decoder into the same periodic state. This is achieved by repeatedly sending a digital initialization code to each chaotic system, driving each of them onto a known periodic orbit and stabilizing the otherwise unstable periodic orbit. The necessary initialization code contains less than 16 bits of information. The transmission step then uses a similar series of controls to steer the trajectories of the periodic orbits to regions of space that are labeled 0 and 1, corresponding to the plain text of a digital message.
Short, et al., Method and Apparatus for Compressed Chaotic Music Synthesis, U.S. patent application Ser. No. 09/437,565 (“Short II”), describes the use of such an initialization step to produce and stabilize known periodic orbits on chaotic systems, which orbits are then converted into sounds that approximate traditional music notes. By sending a digital initialization code to a chaotic system, a periodic waveform can be produced that has a rich harmonic structure and sounds musical. The one-dimensional, periodic waveform needed for music applications is achieved by taking the x-, y-, or z-component (or a combination of them) of the periodic orbit over time as the chaotic system evolves. The periodic waveform represents an analog version of a sound, and by sampling the amplitude of the waveform over time, e.g., using audio standard PCM 16, one can produce a digital version of the sound. The harmonic structures of the periodic waveforms are sufficiently varied that they sound like a variety of musical instruments.
The present invention is a system for the compression and decompression of audio files, including without limitation music and speech files. In summary, a library of basic waveforms associated with a chaotic system is produced, according to Short II and as described in detail hereafter, by applying selected digital initialization codes to the chaotic system. The basic waveforms that can be produced with 16-bit initialization codes range from simple cases that resemble the sum of a few sine waves with an associated frequency spectrum containing only two or three harmonics, to extremely complex waveforms in which the number of significant harmonics is greater than 64. Importantly, the initialization codes are 16 bits regardless of whether the basic waveforms are simple or complex. By contrast, in a linear approach, one would expect the number of bits necessary to produce a waveform to be proportional to the number of harmonics in the waveform. Equally importantly, each initialization code is in one-to-one correspondence with a specific basic waveform, allowing the use of the corresponding initialization code to represent the basic waveform. Then basic waveforms selected from the library are used to approximate a section of audio file.
The basic waveforms that are most closely related to the section of audio file are selected, and a weighted sum of the selected waveforms is used to approximate the section of audio file. Once such a weighted sum is produced that approximates the section of audio file to a specified degree of accuracy, the basic waveforms can be discarded and only the weighting factors; the corresponding initialization codes; and certain frequency information described below are stored in a compressed audio file. The compressed audio file may also contain other implementation-dependent information, e.g. header information defining sampling rates, format, etc. When the compressed audio file is decompressed for playback, the initialization codes are stripped out and used to regenerate the basic waveforms, which are recombined according to the weighting factors in the compressed audio file to reproduce the original section of audio file.
The compressed audio file can be transmitted, or stored for later transmission, to an identical chaotic system for decompression at a remote location. In practice, the remote location does not need the compression part of the system and would only use the decompression part of the system if playback of the section of audio file is all that is desired.
A further degree of compression is often possible and desirable. After finding a suitable weighted sum of basic waveforms, the weighted sum can be examined and any waveforms that contribute less to the overall approximation than a specified threshold can be eliminated. When such waveforms are identified, the corresponding initialization codes can be removed from the compressed audio file. Also, because the compression is done on sections of audio file, it is possible to look at the basic waveforms and the corresponding initialization codes to determine if there is a predictable pattern to the changes in the weighting factors from section to section. If such patterns are detected, further compression of the compressed audio file can be achieved by storing only the requisite initialization code and information about the pattern of changes for the weighting factors.
It is an object of the present invention to create compressed music files for distribution over the Internet. Compression ratios at better than 50-to-1 may be possible, which will allow for the transmission of music files over the Internet with greatly improved download speed. It is possible to estimate the compression ratio for music based on how rapidly the music changes. These estimates indicate that if the music changes on a scale of 0.02 sec, so the important changes in the music occur 50 times a second, then compression of 60-to-1 should be achievable. If the music changes on a scale of 0.04 sec, compression of 120-to-1 should be achievable. It is also an object of the present invention to replace the standard MIDI technology used in the music industry with a system that is simpler, requires less memory and offers more flexible sampling requirements.
It is also an object of the present invention to produce compressed music files that decompress rapidly. For example, in one embodiment an unoptimized C++ program on a 300 MHz processor decompressed at better than three times faster than real time. In a more optimized version, decompression is better than 5 times faster than real time, running on a computer that is roughly equivalent to a 100 MHz processor.
It is yet another object of the present invention to create compressed audio files that are encrypted. For example, music files compressed with the present invention are naturally encrypted in accordance with Short I. In order to be able to decompress properly a compressed music file, it is necessary to have the proper chaotic decompressor. These decompressors could be distributed freely or to a group of registered users, thus allowing for some control over the distribution and reproduction of the compressed music files. Even greater control of the uses of the compressed music files can be achieved by incorporating a secondary layer of a secure chaotic distribution channel, using the technology described in Short I, to encode the digital bits of the compressed music files before transmitting them to a user. Since registered users can be given unique chaotic decoders, it will be possible to place a “security wrapper” around the compressed music files, so that only a registered user will be able to access the music. It will also be possible to structure the security wrapper so that a song can be played only once without paying a fee.